package com.wwy.arithmetic.suanfa;

import com.wwy.arithmetic.suanfa.entry.TreeNode;

/**
 * 二叉树的最小深度
 */
public class ZuiXiaoShenDu {

    //root =
    //[2,null,3,null,4,null,5,null,6]
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(2);
        TreeNode treeNode1 = new TreeNode(3);
        TreeNode treeNode2 = new TreeNode(4);
        TreeNode treeNode3 = new TreeNode(5);
        TreeNode treeNode4 = new TreeNode(6);
        treeNode.setRight(treeNode1);
        treeNode1.setRight(treeNode2);
        treeNode2.setRight(treeNode3);
        treeNode3.setRight(treeNode4);
        int leastNum = getLeastNum(treeNode);
        System.out.println("leastNum = " + leastNum);
    }

    static int getLeastNum(TreeNode node) {
        if (node == null) {
            return 0;
        } else if (node.getLeft() == null) {
            return getLeastNum(node.getRight()) + 1;
        } else if (node.getRight() == null) {
            return getLeastNum(node.getLeft()) + 1;
        } else {
            return Math.min(getLeastNum(node.getLeft()), getLeastNum(node.getRight())) + 1;
        }
    }
}
